package LeetCodeQuestionBank;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 542. 01 矩阵
 * 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
 *
 * 两个相邻元素间的距离为 1 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
 * 输出：[[0,0,0],[0,1,0],[0,0,0]]
 * 示例 2：
 *
 *
 *
 * 输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
 * 输出：[[0,0,0],[0,1,0],[1,2,1]]
 *
 *
 * 提示：
 *
 * m == mat.length
 * n == mat[i].length
 * 1 <= m, n <= 104
 * 1 <= m * n <= 104
 * mat[i][j] is either 0 or 1.
 * mat 中至少有一个 0
 * https://leetcode-cn.com/problems/01-matrix/
 */
public class T542 {
    /**
     * 解题思路： 使用队列 实现广度优先算法 bfs特性就是搜到该点了，该点就是最优解了
     * 新建一个相同大小的二维数组 值都为-1 （利用沉岛思想 ）
     * 先将所有的0 都放入队列 并将所有0的位置更新为0
     * <p>
     * 然后开始bfs 从队首取出一个元素 更新上下左右位置的值（-1表示没有更新）值 = 该元素的值+1 然后将更新后的元素入队
     * 依次类推 知道队列为空
     */
    public int[][] updateMatrix(int[][] mat) {

        int[][] resMat = new int[mat.length][mat[0].length];

        Queue<Element> queue = new LinkedList<>();

        //所有的元素置为-1
        for (int i = 0; i < resMat.length; i++) {
            for (int j = 0; j < resMat[i].length; j++) {
                //如果原数组 该位置为 0  新矩阵该位置同样为0 并将该元素放入队列
                if (mat[i][j] == 0) {
                    resMat[i][j] = 0;
                    queue.add(new Element(i, j, 0));
                } else {
                    resMat[i][j] = -1;
                }
            }
        }

        while (!queue.isEmpty()) {

            Element element = queue.poll();

            int x = element.X;
            int y = element.Y;
            int value = element.value;
            //更新上下左右元素的值
            //上 先判断是否存在该坐标
            if (x > 0 && resMat[x - 1][y] == -1) {
                resMat[x - 1][y] = value + 1;
                queue.add(new Element(x - 1, y, value + 1));
            }

            //下
            if (x < resMat.length - 1 && resMat[x + 1][y] == -1) {
                resMat[x + 1][y] = value + 1;
                queue.add(new Element(x + 1, y, value + 1));
            }

            //左
            if (y > 0 && resMat[x][y - 1] == -1) {
                resMat[x][y - 1] = value + 1;
                queue.add(new Element(x, y - 1, value + 1));
            }

            //右
            if (y < resMat[0].length - 1 && resMat[x][y + 1] == -1) {
                resMat[x][y + 1] = value + 1;
                queue.add(new Element(x, y + 1, value + 1));
            }

        }

        return resMat;

    }

    //定义一种数据结构用于存储元素放入队列 为了代码简洁 没有写get set方法
    static class Element {
        //行坐标
        int X;
        //列坐标
        int Y;
        //值
        int value;

        public Element(int x, int y, int value) {
            X = x;
            Y = y;
            this.value = value;
        }
    }
}
